
import java.util.*;

//链表中倒数K个节点
//输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
//如果该链表长度小于k，请返回一个长度为 0 的链表

public class Solution {
    public class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
        }
    }

    //解法一  栈
    public ListNode FindKthToTail (ListNode pHead, int k) {
        Stack<ListNode> stack = new Stack<>();
        LinkedList<ListNode> list = null;
        ListNode cur = pHead;
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        int size = stack.size();
        if(k > size || k == 0){
            return null;
        }else if(k == size){
            return pHead;
        }else{
            for(int i = 1; i < k ;i++){
                stack.pop();
            }
        }
        return stack.pop();
    }

    //解法二 快慢指针
    //第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动
    // 当第一个指针到链表的末尾的时候，返回第二个指针即可
    public ListNode FindKthToTail2(ListNode pHead,int k){
        ListNode fast = pHead;
        ListNode slow = pHead;
        for(int i = 1; i <= k; i++){
            if(fast != null){
                fast = fast.next;
            }else{
                return slow = null;
            }
        }
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
